
public class Leetcode661 {
    /*private static final int[][] ABOUT = new int[][]{
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1}, {0, 0}, {0, 1},
            {1, -1}, {1, 0}, {1, 1},
    };

    public int[][] imageSmoother(int[][] img) {
        int m = img.length;
        int n = img[0].length;
        int[][] res = new int[m][n];
        for (int row = 0; row < img.length; row++) {
            for (int column = 0; column < img[row].length; column++) {
                int current = 0;
                int currentNumber = 0;
                for (int[] index : ABOUT) {
                    int currentRow = index[0] + row;
                    int currentColumn = index[1] + column;
                    if (currentRow >= 0 && currentRow < m && currentColumn >= 0 && currentColumn < n) {
                        ++currentNumber;
                        current += img[currentRow][currentColumn];
                    }
                }
                res[row][column] = current / currentNumber;
            }
        }

        return res;
    }*/

    public int[][] imageSmoother(int[][] img) {
        int m = img.length;
        int n = img[0].length;
        int[][] dp = new int[m][n];
        int count = 0;
        for (int row = 0; row < img.length; row++) {
            for (int column = 0; column < img[row].length; column++) {
                count += img[row][column];
                dp[row][column] = count;
            }
        }

        int[][] res = new int[m][n];
        for (int row = 0; row < img.length; row++) {
            for (int column = 0; column < img[row].length; column++) {
                int up = Math.max(0, row - 1);
                int left = Math.max(0, column - 1);
                int down = Math.min(m - 1, row + 1);
                int right = Math.min(n - 1, column + 1);

                res[row][column] = (dp[down + 1][right + 1] - dp[up][right + 1] - dp[down + 1][left] + dp[up][left]) / ((down - up + 1) * (right - left + 1));
            }
        }

        return res;
    }

}
